\documentclass[journal,9pt]{IEEEtran}

\ifCLASSINFOpdf
\else
\fi
\usepackage{float}
\usepackage{subfig}
\usepackage{url}
\usepackage{lettrine}
\usepackage{graphicx}
\usepackage[cmex10]{amsmath}
\usepackage{listings}
\interdisplaylinepenalty=2500
\graphicspath{{img/}}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\hyphenation{op-tical wire-less net-works}
\usepackage{newcent}

\begin{document}
\title{Optical Flow Game Using Lucas-Kanade Algorithm}
\author{Kaan~Ak\c{s}it
\thanks{The authors is with the Optical Microsystems Laboratory, Ko\c{c} University, Istanbul,
34450 TURKEY (e-mail: kaksit@ku.edu.tr).}}
\markboth{Digital Image and Video Processing/ June~2011}
{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls
for the Journal of Optical Communications and Networking}
\IEEEpubid{0000--0000/00\$00.00~\copyright~2011 Digital Image and Video Processing}


\maketitle
\begin{abstract}
This paper introduces a concept game using one of the optical flow algorithm so called Lucas-Kanade algorithm. The aim of this game is to derive possibilities using light-weight image processing algorithms in the gaming sector. Possible impact of such a derivation is to release an open-source game which can be played in various operating systems and platforms. The tools to build the software explained in this paper are all from open-source ecology such as Subversion, Python, Pygame, OpenCV and its bindings. Moreover the software implementation can be examined under \cite{bulutus}.
\end{abstract}
\begin{IEEEkeywords}
Image processing, Lucas-Kanade algorithm, Python, Open-source, OpenCV, Pygame.
\end{IEEEkeywords}
\IEEEpeerreviewmaketitle

\section{Introduction}
\label{section:introduction}
\lettrine{T}{he} gaming industry is driven with some certain elements. In the near past, one perspective that heavily effect this industry is the technologies that allow to user to interact with the software in different ways. Most common methods are using game-pads, keyboards and mouse in the near past. But with the help of image processing now it is possible to add an another interaction method. This trend is so called touch free gaming. With the current technologies, It is possible to detect certain movements of the users and  it is even possible to label the movements. Some of the respected companies such as SONY heavily invest on these concepts. $PlayStation^{\textregistered}$ eye from SONY is a peripheral that allow the gaming console to capture photographs from the scene of the gamers ,see \cite{playstationeye}. One of the most popular example is Kinect from Microsoft, see \cite{kinect}. Figure \ref{fig:products} shows the existing products with the described concept. This paper is based on introducing the system by using light-weight version of this approach and motivation explained in above. One other fact that has to be pointed out is the fact that the cost and availability of cameras for computers has increased heavily in the near past. Thus, it is possible to turn any kind of platform with a camera into a gaming console or an remote user-interface.

\begin{figure}[H]
  \centering
  \subfloat[Kinetic from Microsoft.]{\label{fig:kinetic}\includegraphics[width=0.23\textwidth]{kinect}} \hspace{2mm}      
  \subfloat[Playstation eye from SONY.]{\label{fig:playstationeye}\includegraphics[width=0.15\textwidth]{playstationeye}} \hspace{2mm}             
  \caption{Products from various companies.}
  \label{fig:products}
\end{figure}

The investigation of this concept is implemented to free to access tools from open-source ecology. The preferred programming language is Python, see \cite{python}. Some parts of the implementation is done using Numpy/Scipy, OpenCV and Pygame libraries, see \cite{scipy}, \cite{opencv} and \cite{pygame}. All the implementation is done under Pardus Linux, see \cite{pardus}. 

The game discussed in this paper can be introduced as follows: the character named as "$bulutus$", see Figure \ref{fig:bulutus} is trying to 
intersect and destroy the enemy ships in the gaming scene, see Figure \ref{fig:enemy}. Note that graphics are interpreted in a anaglyph 3D fashion, graphics can be seen properly using red-cyan glasses. 

\begin{figure}[H]
  \centering
  \subfloat[Graphics for the main character so called "$bulutus$".]{\label{fig:bulutus}\includegraphics[width=0.10\textwidth]{cloud3d}} \hspace{2mm}      
  \subfloat[Graphics for the enemy character.]{\label{fig:enemy}\includegraphics[width=0.10\textwidth]{ship3d}} \hspace{2mm}             
  \caption{Graphical pieces from the game.}
  \label{fig:graphics}
\end{figure}
\IEEEpubidadjcol

The user moves the character by pushing it towards to enemy, each time an intersection occurs an enemy is destroyed and the user gains some points. If the character is pushed in a position not inside the gaming scene, then the character lost a life. In the final implementation it is thought to have extra bonus characters to have a more complicated game structure and an more fun game to play.

\section{Theory}
\label{section:theory}
To detect the motion to push the main character to kill some enemy, there is a need of a motion detection. The chosen method in this case is an old and fast method so called Lucas-Kanade. This part explains how it is implemented inside the code. As described in \cite{tekalp1995digital} and \cite{woods2006multidimensional}, velocity components in both x-axis and y-axis can be found using Equation \ref{equ:lucaskanade}. To derive the Equation given in \ref{equ:lucaskanade}, first step is the formation of velocity, time derivative, x-axis derivative and y-axis derivative as in Equation \ref{equ:matrices}. Using optical flow equation, one can derive the Equation \ref{equ:lucaskanade} by using Equation \ref{equ:solve}.

\begin{equation}
\label{equ:matrices}
\begin{split}
A = \begin{bmatrix}
I_x(q_1) & I_y(q_1) \\
I_x(q_2) & I_y(q_2) \\
\vdots  & \vdots  \\
I_x(q_n) & I_y(q_n) 
\end{bmatrix},
\quad\quad
\\
v = 
\begin{bmatrix}
V_x\\
V_y
\end{bmatrix},
\quad \mbox{and}\quad
b = 
\begin{bmatrix}
-I_t(q_1)\\
-I_t(q_2)\\
\vdots \\
-I_t(q_n)
\end{bmatrix} 
\end{split}
\end{equation}


\begin{equation}
\label{equ:solve}
\begin{split}
A^T A v=A^T b
\end{split}
\end{equation}

\begin{equation}
\label{equ:lucaskanade}
\begin{split}
\mathrm{v}=(A^T A)^{-1}A^T b
\end{split}
\end{equation}

Equation \ref{equ:lucaskanade} can be written in matrix format as in Equation \ref{equ:lucaskanadematrix}. Format in Equation \ref{equ:lucaskanadematrix} is used in the implementation. Each component used in Equation \ref{equ:lucaskanadematrix} is calculated and the matrices are formed using two iteration operator to scan whole image. Note that whole theory explained here is valid for non-pyramidal approach of Lucas-Kanade algorithm.

\begin{equation}
\label{equ:lucaskanadematrix}
\begin{split}
\begin{bmatrix}
V_x\\
V_y
\end{bmatrix} 
=
\begin{bmatrix}
\sum_i I_x(q_i)^2       & \sum_i I_x(q_i)I_y(q_i) \\
\sum_i I_x(q_i)I_y(q_i) & \sum_i I_y(q_i)^2 
\end{bmatrix}^{-1}\\
\begin{bmatrix}
-\sum_i I_x(q_i)I_t(q_i)\\
-\sum_i I_y(q_i)I_t(q_i)
\end{bmatrix}
\end{split}
\end{equation}

\section{Implementation}
\label{section:implementation}
This section describes and discuss about the implementation of both image processing part and the game classes.
\subsection{Implementation of Lucas-Kanade algorithm}
As described in Equation \ref{equ:lucaskanadematrix}, implementation of Lucas-Kanade algorithm is done as in below using Numpy/Scipy library:

\lstset{language=Python,breaklines=true}
\lstinputlisting[language=Python,firstline=165,lastline=201]{../src/main.py}

The performance of the above code in a rectangular surface that contains $25x25$ pixels is $11$ frames per second with a computer over average hardware (Intel Core 2 Duo CPU 2.53 GHz). Note that this implementation does not use the graphical central processing unit instead it is using central processing unit. This result is satisfactory for such amount of pixels. 
\begin{figure}[H]
  \centering
  \subfloat[First sample frame.]{\label{fig:sampleframe1}\includegraphics[width=0.21\textwidth]{sampleframe1}} \hspace{2mm} 
  \subfloat[Second sample frame.]{\label{fig:sampleframe2}\includegraphics[width=0.21\textwidth]{sampleframe2}} \hspace{2mm} 
  \subfloat[Result of the implementation using Figure \ref{fig:bulutus} and Figure \ref{fig:bulutus}, note that motion vectors in both direction is combined in this Figure.]{\label{fig:train}\includegraphics[width=0.21\textwidth]{train}} \hspace{2mm}                 
  \caption{Sample result using sample image with $15x15$ window size.}
  \label{fig:demo}
\end{figure}

Note that in the implementation a Gaussian filter is used to blur the input image to avoid false motion vectors due to error originated from camera pixels. Image is transformed into YUV color space and then processed using the above implementation. Using above implementation Figure \ref{fig:demo} is derived.

To see how the implemented function processes sample images, one can uncomment line $249$ in $main.py$ file and run the $main.py$ function using Python interpreter located in the $trunk/src/$ folder of the project page, see \cite{bulutus}. For a bigger amount of pixel number an optimised code is used from the OpenCV library. The implementation of the optimised algorithm can be seen in below and note that code is optimised to work with a graphical processing unit:

\lstset{language=Python,breaklines=true}
\lstinputlisting[language=Python,firstline=141,lastline=163]{../src/main.py}

The performance of this code on same hardware is $7$ frames per second for $640x480$ pixels. For a $25x25$ pixel rectangle, it performance even better up to $31$ frames per second. To increase the performance of the implemented game, OpenCV version of Lucas-Kanade algorithm is used instead. Inside the game, motion vectors are calculated only in the rectangle that the main character covers. As a result if there is any motion inside the rectangle, the rectangle position is updated by using the motion vectors. All the motion vectors are averaged and the average is used to move the main character rectangle.

\subsection{Implementation of gaming classes}

To implement the game, a library entitled as Pygame is used. It contains good enough functions to build a 2D game from the scratch. It contains built-in functions to capture images from a $V4L2$ supported camera. To capture the images from web camera, the built-in functions are used as inside $trunk/src/main.py$ at lines $61-81$, these lines contains a class so called $camera$. To form the graphical user interface another class is built inside $trunk/src/main.py$ at lines $14-59$. Beside these one can examine all the bindings used inside the game as in below header:

\lstset{language=Python,breaklines=true}
\lstinputlisting[language=Python,firstline=1,lastline=12]{../src/main.py}

The main flow function which runs in an infinite loop can be best described as in Figure \ref{fig:algorithm}, see lines $226-272$ at $trunk/src/main.py$.

\begin{figure}[H]
\setlength{\unitlength}{0.14in}
\centering
\begin{picture}(32,7)
\put(0,6){Start}
\put(0,5.5){\vector(1,0){3}}
\put(3,4){\framebox(5,3){Initialize}}
\put(8,5.5){\vector(1,0){2}}
\put(10,4){\framebox(6,3){Event handle}}
\put(16,5.5){\vector(1,0){2}}
\put(18,4){\framebox(5,3){Capture}}
\put(20.5,4){\vector(0,-1){1}}
\put(17,0){\framebox(7,3){Optical flow}}
\put(17,1.4){\vector(-1,0){3}}
\put(4,0){\framebox(10,3){Update elements}}
\put(12,3){\vector(0,1){1}}
\end{picture}
\caption{Sketch of algorithm at an infinite loop.}
\label{fig:algorithm}
\end{figure}

Figure \ref{fig:algorithm} can be summarized as follows: Initialize part initialize the necessary images to be used inside the game and define necessary variables. The next step is the start of the infinite loop. Event handle box checks for the $keypress$ event which corresponds to pressing $ESC$ key on the keyboard and the same box also checks for $QUIT$ event which corresponds to hitting on the x sign on the upper right hand side of the window. Capture box captures images using the self-coded class $camera$. The images taken from the camera are fed into the Optical flow box. Using lucas-kanade, motion vectors are derived and the position of the main character is updated accordingly. The enemies are also updated using the self-coded class so called $enemy$, see lines $96-112$ at $trunk/src/main.py$. The whole coding typically runs at $20-30$ frames per second on an average computer. Note that performance of $11$ frames per second is good enough to the run the game fluent. Example output from the graphical user interface of the game can be examined under Figure \ref{fig:gamewindow}.

\begin{figure}[H]
\centering
\includegraphics[width=2.6in]{output}
\caption{Sample output from game window.}
\label{fig:gamewindow}
\end{figure}

\section{Conclusion}
\label{section:conclusion}
A concept game using optical flow game is implemented and it is currently at its alpha version. The game runs fast enough on an average computer and contains a light-weight algorithm. Since the game is implemented using Python programming language, it is a platform free game. Only boundary at this point is the self-coded $camera$ class which is unfortunately only valid for Mac OS X and Linux systems. The code is available under the trunk of \cite{bulutus}. One can copy the whole files of the game using command in below under Linux or Mac OS X system:

\begin{lstlisting}
svn checkout http://bulutus.googlecode.com/svn/trunk/ bulutus-read-only
\end{lstlisting}

The game can be imported into various platforms such as ARM based main-boards, example: BeagleBoard, see \cite{beagleboard}. By doing so and using a pico-projector a portal game platform can be achieved. The next phase of this project is to finalize the game and release a set-up both for Microsoft Windows, Mac OS X and Linux operating systems. As a future work, pyramidal approach of Lucas-Kanade algorithm can be implemented to increase the accuracy of calculated motion vectors. One more further step is to implement creating a skeleton from the image approach to relate some specific motion into different inputs. One can watch a clip to review the current state of alpha version of the game under \cite{youtube}.


\section{Acknowledgement}
\label{section:acknowledgement}
The author would like to thank to Professor Murat Tekalp and G\"{o}ktu\u{g} G\"{u}rler for providing the chance to work on this project in the scope of the digital image and video processing lecture. The author would also like to thank to Google Code for providing free subversion based online space for the project.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{ieeetr}
\bibliography{references}
\end{document}



